package heap

import (
	"gitee.com/kklt1996/data-structure/array"
	"gitee.com/kklt1996/data-structure/util"
)

type MinHeap struct {
	data *array.SliceArray

	/*
		使用comparator比较堆中元素大小,实现common.CompareAble接口和传入比较器形式二选一
		1 thisValue＞compareValue
		0 thisValue=compareValue
		-1 thisValue<compareValue
	*/
	comparator func(thisValue interface{}, compareValue interface{}) int
}

func (heap MinHeap) GetSize() int {
	return heap.data.Size()
}

func (heap MinHeap) IsEmpty() bool {
	return heap.data.IsEmpty()
}

func (heap MinHeap) Add(value interface{}) {
	heap.data.AddLast(value)
	heap.siftUp(heap.data.Size() - 1)
}

func (heap MinHeap) FindTop() (interface{}, error) {
	return heap.data.GetFirst()
}

func (heap MinHeap) ExtractTop() (interface{}, error) {
	minValue, err := heap.data.GetFirst()
	if err != nil {
		return nil, err
	}
	heap.data.Set(0, nil)
	lastValue, nil := heap.data.GetLast()
	heap.data.Set(0, lastValue)
	_, _ = heap.data.RemoveLast()
	if heap.data.Size() > 1 {
		heap.siftDown(0)
	}
	return minValue, nil
}

func (heap MinHeap) Replace(value interface{}) (interface{}, error) {
	minValue, err := heap.data.GetFirst()
	if err != nil {
		return nil, err
	}
	heap.data.Set(0, value)
	heap.siftDown(0)
	return minValue, nil
}

func (heap MinHeap) siftDown(index int) {
	size := heap.data.Size()
	indexValue, _ := heap.data.Get(index)
	for {
		leftChildIndex := heap.leftChildIndex(index)
		if leftChildIndex >= size {
			break
		}

		minChildValue, _ := heap.data.Get(leftChildIndex)
		minChildIndex := leftChildIndex
		rightChildIndex := heap.rightChildIndex(index)
		if rightChildIndex < size {
			rightChileValue, _ := heap.data.Get(rightChildIndex)
			if heap.compare(rightChileValue, minChildValue) < 0 {
				minChildValue = rightChileValue
				minChildIndex++
			}
		}

		if heap.compare(minChildValue, indexValue) < 0 {
			heap.data.Set(index, minChildValue)
			heap.data.Set(minChildIndex, indexValue)
			index = minChildIndex
		} else {
			break
		}
	}
}

func (heap MinHeap) siftUp(index int) {
	indexValue, _ := heap.data.Get(index)
	for index > 0 {
		parentIndex := heap.parentIndex(index)
		parentValue, _ := heap.data.Get(parentIndex)

		if heap.compare(indexValue, parentValue) < 0 {
			heap.data.Set(index, parentValue)
			heap.data.Set(parentIndex, indexValue)
			index = parentIndex
		} else {
			break
		}
	}
}

func (heap MinHeap) compare(thisValue interface{}, compareValue interface{}) int {
	if heap.comparator != nil {
		return heap.comparator(thisValue, compareValue)
	}
	return util.DefaultComparator(thisValue, compareValue)
}

/*
	返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
*/
func (heap MinHeap) parentIndex(index int) int {
	return (index - 1) / 2
}

/*
	返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
*/
func (heap MinHeap) leftChildIndex(index int) int {
	return index*2 + 1
}

/*
	返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
*/
func (heap MinHeap) rightChildIndex(index int) int {
	return index*2 + 2
}
